package com.mjf.search;

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找
 * <p>
 * 要求数组有序
 * </p>
 */
public class BinarySearch {

    private int[] arr;

    @Before
    public void init() {
        arr = new int[]{1, 8, 10, 89, 89, 89, 89, 89, 89, 89, 1000, 1234};
    }

    /**
     * 二分查找-指定数据其中一个索引
     */
    @Test
    public void testBinarySearch() {
        int index = binarySearch(arr, 0, arr.length - 1, 1234);
        if (index == -1) {
            System.out.println("数据没查到");
        } else {
            System.out.println("数据下标为：" + index);
        }
    }

    /**
     * 二分查找-指定数据的所有索引
     */
    @Test
    public void testBinarySearchAllIndex() {
        List<Integer> index = binarySearchAllIndex(arr, 0, arr.length - 1, 89);
        if (index.size() == 0) {
            System.out.println("数据没查到");
        } else {
            System.out.println("数据下标为：" + index);
        }
    }

    /**
     * 二分查找-指定数据其中一个索引
     *
     * @param arr   数组
     * @param left  数组左边界索引
     * @param right 数组右边界索引
     * @param value 待查找数据
     */
    public static int binarySearch(int[] arr, int left, int right, int value) {
        if (left > right) {
            return -1;
        }

        // 中间索引
        int mid = (left + right) / 2;

        if (arr[mid] > value) {
            // 中间元素大于待查询元素，向左递归
            return binarySearch(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            // 中间元素小于待查询元素，向右递归
            return binarySearch(arr, mid + 1, right, value);
        } else {
            return mid;
        }
    }

    /**
     * 二分查找-指定数据的所有索引
     *
     * @param arr   数组
     * @param left  数组左边界索引
     * @param right 数组右边界索引
     * @param value 待查找数据
     */
    public static List<Integer> binarySearchAllIndex(int[] arr, int left, int right, int value) {
        if (left > right) {
            return new ArrayList<>();
        }

        // 中间索引
        int mid = (left + right) / 2;

        if (arr[mid] > value) {
            // 中间元素大于待查询元素，向左递归
            binarySearchAllIndex(arr, left, mid - 1, value);
        } else if (arr[mid] < value) {
            // 中间元素小于待查询元素，向右递归
            binarySearchAllIndex(arr, mid + 1, right, value);
        } else {
            ArrayList<Integer> indexList = new ArrayList<>();
            // 遍历左边所有相等元素
            int temp = mid - 1;
            while (arr[temp] == value) {
                indexList.add(temp);
                temp--;
            }
            Collections.reverse(indexList);
            indexList.add(mid);
            // 遍历右边所有相等元素
            temp = mid + 1;
            while (arr[temp] == value) {
                indexList.add(temp);
                temp++;
            }
            return indexList;
        }

        return new ArrayList<>();
    }
}
